 /********************************************************************************************\
 * libeds - extensible data structures library                                                *
 * Copyright (C) 2006, Dan Kruchinin, <just.asgard@gmail.com>                                 *
 *                                                                                            *
 * -> trees/bin_tree.h                                                                        *
 * Basic bare bones of binary tree. This is some base, that can be used                       *
 * as a fundamental part of any _binary_ tree.                                                *
 *                                                                                            *
 * This library is free software; you can redistribute it and/or modify it under the terms of *
 * the GNU Lesser General Public License as published by the Free Software Foundation;        *
 * either version 2.1 of the License, or (at your option) any later version.                  *
 *                                                                                            *
 * This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;  *
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  *
 * See the GNU Lesser General Public License for more details.                                *
 *                                                                                            *
 * You should have received a copy of the GNU Lesser General Public License along with this   *
 * library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,  *
 * Boston, MA 02111-1307 USA                                                                  *
 \********************************************************************************************/

#ifndef DS_BIT_H
#define DS_BIT_H

#include "ds.h"

#define BIT_LEFT  0
#define BIT_RIGHT 1

/* binary tree node */
typedef struct bit_node {
  /* public: */
  void* key;     /* key is optional if DS_FNOKEY option enabled in tree. */
  void* value;
  struct bit_node* parent;
  struct bit_node* left;
  struct bit_node* right; 
  /* private */
  int _nofnodes; /* number of subnodes */
  void* _pvt;    /* tree-specific information(any) */
} bit_node;

typedef int (*bit_copy_func_t)(bit_node*, void*, void*);
typedef ds_cmp_t (*bit_cmp_func_t)(const void*, const void*);
typedef void (*bit_delete_func_t)(void*, void*);

/* default binary tree "user-space functions" */
typedef struct _bit_funcs {
  bit_copy_func_t copy;
  bit_cmp_func_t cmp;
  bit_delete_func_t delete;
} _bit_funcs;

/* binary tree basic structure */
struct _bit {
  bit_node* root;  /* tree indeed */
  _bit_funcs funcs; /* "user-space" functions */
  ds_flags_t flags; /* behaivour flags */
};

#define BIT_SEARCH_ERR							\
  (bit_node*)(-1)

#define BIT_CONVERTION(tree, tree_type)			\
  ((tree_type*)(tree))
#define bit2base_tree(tree)						\
  BIT_CONVERTION(tree, bin_tree)

/* this macro makes life easier. it adds default functions defenitions in your tree */
#define BIT_DEFAULT_FUNCS(name)										\
  bit_node* (*root)(const struct _bit*);							\
  int (*insert)(struct _bit*, void*, void*);						\
  int (*delete)(struct _bit*, bit_node*);							\
  bit_node* (*find)(struct _bit*, const void*);						\
  bit_node* (*node_left)(const bit_node*);							\
  bit_node* (*node_right)(const bit_node*);							\
  bit_node* (*node_parent)(const bit_node*);						\
  bit_node* (*node_brother)(const bit_node*);						\
  bit_node* (*node_successor)(bit_node*);							\
  bit_node* (*node_predecessor)(bit_node*);							\
  int (*node_height)(bit_node*);									\
  int (*node_ipl)(bit_node*);										\
  int (*node_epl)(bit_node*);										\
  int (*node_subnodes)(const bit_node*);

typedef struct bin_tree {
  struct _bit* tree;
  BIT_DEFAULT_FUNCS(struct bin_tree);
} bin_tree;

/* register default tree functions(they can be redirected) */
#define BIT_REG_DEFAULT_FUNCS(tree)										\
  (tree)->root = _bit_root;												\
  (tree)->insert = _bit_insert;											\
  (tree)->delete = _bit_delete;											\
  (tree)->find = _bit_find;												\
  (tree)->node_left = _bit_node_left;									\
  (tree)->node_right = _bit_node_right;									\
  (tree)->node_parent = _bit_node_parent;								\
  (tree)->node_successor = _bit_node_successor;							\
  (tree)->node_predecessor = _bit_node_predecessor;						\
  (tree)->node_brother = _bit_node_brother;								\
  (tree)->node_height = _bit_node_height;								\
  (tree)->node_ipl = _bit_node_ipl;										\
  (tree)->node_epl = _bit_node_epl;										\
  (tree)->node_subnodes = _bit_node_subnodes;


void _bit_init_main(void);
struct _bit* _bit_allocate(void);
void _bit_destroy(struct _bit*);
bit_node* _bit_node_new(void);
void _bit_node_destroy(bit_node*);
bit_node* _bit_rotate_left(struct _bit*, bit_node*);
bit_node* _bit_rotate_right(struct _bit*, bit_node*);
bit_node* _bit_root(const struct _bit*);
int _bit_insert(struct _bit*, void*, void*);
int _bit_delete(struct _bit*, bit_node*);
bit_node* _bit_find(struct _bit*, const void*);
bit_node* _bit_node_left(const bit_node*);
bit_node* _bit_node_right(const bit_node*);
bit_node* _bit_node_parent(const bit_node*);
bit_node* _bit_node_brother(const bit_node*);
bit_node* _bit_node_successor(bit_node*);
bit_node* _bit_node_predecessor(bit_node*);
void _bit_recount_nodes(bit_node*);
int _bit_node_height(bit_node*);
int _bit_node_ipl(bit_node*);
int _bit_node_epl(bit_node*);
int _bit_node_subnodes(const bit_node*);

#endif /* DS_BIT_H */
